/*
 * Copyright (c) 2010 Mathew Hall, University of Sheffield.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided
 * with the distribution.
 *
 * Neither the name of the University of Sheffield nor the names of its
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */
package search.fitnessfunctions;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import primitives.cluster.ClusterLeaf;
import primitives.cluster.ClusterHead;
import primitives.cluster.IClusterLevel;
import primitives.cluster.ClusterUtils;
import primitives.graph.Node;
import primitives.graph.Transition;

public class MQFitnessFunction extends TreeFitnessFunction {

    /**
     * 
     */
    private static final long serialVersionUID = 7120957201639200697L;

    public double evaluate(ClusterHead tree) {
        List<ClusterLeaf> leaves = tree.getLeaves();
        int k = leaves.size(); // TODO: can't use leaves because they've all
        // just got one element
        Set<IClusterLevel> parents = new HashSet<IClusterLevel>();
        for (ClusterLeaf leaf : leaves) {
            parents.add(ClusterUtils.findParent(leaf, tree));
        }
        Set<IClusterLevel> par = new HashSet<IClusterLevel>();
        for (IClusterLevel p : parents) {
            par.add(ClusterUtils.findParent(p, tree));
        }
        k = parents.size();

        double intra = 0;
        double inter = 0;
        for (IClusterLevel c : parents) {
            intra += calculateIntra(c);
        }
        if (k > 1) {
            for (IClusterLevel c : parents) {
                for (IClusterLevel c2 : parents) {
                    inter += calculateInter(c, c2);
                }
            }

            double res = ((intra / k) - (inter / ((k * 1.0 * (k - 1)) / 2.0)));
            if (res < 0.0) {
                return 0.0;
            }
            return res;
        } else {

            return intra;

        }

    }

    public static double calculateIntra(IClusterLevel cluster) {
        double mu = 0;
        // System.out.println("hit a cluster in intra");
        for (Node n : cluster.getNodes()) {
            // System.out.println("doing node " + n);
            Set<Transition> s = n.getTransitionsAsT();
            for (Transition t : s) {
                // System.out.println("doing a transition");
                if (cluster.contains(t.getDestinationNode())) {
                    mu++;
                    // System.out.println("mu++");
                }
            }
        }
        return mu / (1.0 * cluster.getSize() * cluster.getSize());
    }

    public static double calculateInter(IClusterLevel i, IClusterLevel j) {
        // System.out.println("Hit inter");
        if (i == j) {
            return 0;
        }
        double epsilon = 0;
        for (Node n : i.getNodes()) {
            Set<Transition> s = n.getTransitionsAsT();
            for (Transition t : s) {
                if (j.contains(t.getDestinationNode())) {
                    epsilon++;
                    // System.out.println("epsilon++");
                }
            }
        }
        return epsilon / (2.0 * i.getSize() * j.getSize());
    }
}
